package leetcode.code0403;

/**
 * 从哪能到这来 <br>
 * 递归可以 dp不行 错误答案
 *
 * @author CaoYu
 * @date 2021年10月5日
 * @description
 */
public class Solution2 extends Solution403 {

	@Override
	public boolean canCross(int[] stones) {
		if (stones[1] != 1)
			return false;
		if (stones.length == 2)
			return true;
		int[] ks = new int[stones.length];
		ks[0] = 1;
		ks[1] = 1;
		return this.canCross(stones, 2, ks);
	}

	/**
	 * 上一步是k, 现在站在stone上, 能不能跳到最后
	 *
	 * @param stones
	 * @param stone
	 * @param k
	 * @return
	 */
	private boolean canCross(int[] stones, int stone, int[] ks) {
		if (stone == stones.length)
			return true;
		for (int i = 1; i < stone; i++) {
			for (int j = ks[i] - 1; j <= ks[i] + 1; j++) {
				if (stones[stone] == stones[i] + j) {
					ks[stone] = j;
					boolean can = this.canCross(stones, stone + 1, ks);
					if (can)
						return true;
				}
			}
		}
		return false;
	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		so.debug1();
		so.debug2();
		so.debug3();
	}

}
